package main

/**
145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
*/

//type TreeNode struct {
//	Val   int
//	Left  *TreeNode
//	Right *TreeNode
//}

/**
方法一:递归
*/
func postorderTraversal(root *TreeNode) (nums []int) {
	postRec(root, &nums)
	return
}

func postRec(root *TreeNode, nums *[]int) {
	if root == nil {
		return
	}
	postRec(root.Left, nums)
	postRec(root.Right, nums)
	*nums = append(*nums, root.Val)
}

/**
方法二:栈迭代
*/
func postorderTraversal2(root *TreeNode) (nums []int) {
	if root == nil {
		return
	}
	treeStack := make([]*TreeNode, 0) //栈右进右出,用于存储节点遍历顺序的
	treeStack = append(treeStack, root)
	rootStack := make([]*TreeNode, 0) //栈右进右出,用于存储后序处理的root节点的

	for len(treeStack) > 0 {
		root = treeStack[len(treeStack)-1]                                                      //出栈操作
		treeStack = treeStack[:len(treeStack)-1]                                                //出栈操作
		if len(rootStack) == 0 || (len(rootStack) > 0 && root != rootStack[len(rootStack)-1]) { //表示不是历史已经后序遍历的节点
			treeStack = append(treeStack, root)
			rootStack = append(rootStack, root)
			if root.Right != nil {
				treeStack = append(treeStack, root.Right)
			}
			if root.Left != nil {
				treeStack = append(treeStack, root.Left)
			}
		} else if len(rootStack) > 0 && root == rootStack[len(rootStack)-1] {

			nums = append(nums, root.Val)
			rootStack = rootStack[:len(rootStack)-1]
		}
	}
	return
}
